import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * Provides methods for searching and traversing graphs using four algorithms:
 * BFS, DFS, Dijkstra's, and Prim's.
 */
public class GraphAlgorithms {

	/**
	 * Searches the graph for a path from start to goal, using the provided
	 * DataStructure as the frontier data structure.
	 * 
	 * @param start
	 *            The starting vertex
	 * @param goal
	 *            The goal vertex
	 * @param frontier
	 *            The DataStructure to use for the frontier
	 * @return The first path encountered from start to goal, if one exists, or
	 *         null otherwise
	 */
	public static <V extends Vertex<V>> Path<V> search(V start,V goal, DataStructure<V> frontier) {
		java.util.LinkedList<V> queue = new java.util.LinkedList<V>();
		boolean done = false;
		Path<V> outPath = new Path<V>(start);
		Path<V> curPath = null;
		queue.add(start);
		frontier.add(new Path<V>(start));
		while(!frontier.isEmpty() && !done)
		{
			curPath = frontier.remove();
			List<Pair<V>> adj = curPath.getLastVertex().getAdjacent();
			
			for(int i = 0; i < adj.size()&&!done;i++)
			{
				Pair<V> pair = adj.get(i);
				V vert = pair.getVertex();
				if(!queue.contains(vert))
				{
					queue.add(vert);
					outPath = new Path<V>(outPath,pair);
					frontier.add(new Path<V>(curPath,pair));
					if(vert.equals(goal))
					{	
						done = true;
						curPath = new Path<V>(curPath,pair);
					}
				}
			}
			
		}
		
		return curPath;
	}

	/**
	 * Traverses the graph using the provided DataStructure as the frontier data
	 * structure. The result is a list of paths from the starting vertex to
	 * every other vertex.
	 * 
	 * @param start
	 *            The starting vertex
	 * @param frontier
	 *            The DataStructure to use for the frontier
	 * @return Paths from the starting vertex to every other vertex
	 */
	
	public static <V extends Vertex<V>> List<Path<V>> traverse(V start, DataStructure<V> frontier) {
		
		List<Path<V>> queue = new ArrayList<Path<V>>();
		Path<V> outPath = new Path<V>(start);
		Set<String> strSet = new HashSet<String>();
		Path<V> curPath = null;
		queue.add(outPath);
		frontier.add(new Path<V>(start));
		while(!frontier.isEmpty())
		{		
			curPath = frontier.remove();
			List<Pair<V>> adj = curPath.getLastVertex().getAdjacent();
			for(int i = 0; i<adj.size();i++)
			{
				Pair<V> pair = adj.remove(i);
				V vert = pair.getVertex();
				if(!strSet.contains(vert.toString()))
				{
					
					strSet.add(vert.toString());
					queue.add(new Path<V>(outPath,pair));
					outPath = new Path<V>(outPath,pair);
					frontier.add(new Path<V>(curPath,pair));
				}
			}
		}
		
		return queue;
	}
}
